package cn.cxq.learning.dynamic_programming;

/**
 * 牛客题霸-全部题目
 * 走网格
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：128
 * 本题知识点： 动态规划
 *  算法知识视频讲解
 * 题目描述
 * 一个nxm的网格中，起点在(1,1)，终点在(n,m)，网格中有一块不能走的矩形区域，左下坐标为(x0,y0)，右上坐标为(x1,y1)，求从起点到终点的路径条数。
 *
 *
 * 示例1
 * 输入
 * 复制
 * 4,4,2,2,3,3
 * 返回值
 * 复制
 * 2
 * 说明
 * 只有两条可达路径
 * 备注:
 * 1\leq n,m \leq 10^31≤n,m≤10
 * 3
 *  ，1\leq x0\leq x1\leq n1≤x0≤x1≤n，1\leq y0\leq y1\leq m1≤y0≤y1≤m , 答案可能很大请对1000000007取模
 */
public class GetNumberOfPath {
    // 动态规划解题： 其实走到终点的路径就等于走到终点右边和走到终点下边的路径条数，以此类推
    public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        if (n == 0 || m == 0) {
            return 0;
        }

        int[][] dp = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                } else {
                    if ((i >= x0 - 1 && i <= x1 - 1) && (j >= y0 - 1 && j <= y1 - 1)) {
                        dp[i][j] = 0;
                    } else {
                        dp[i][j] = ((i - 1 >=0 ? dp[i - 1][j] : 0) + (j - 1 >=0 ? dp[i][j - 1] : 0))%1000000007;
                    }
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}
